package bin_tree;

/**
 * @author shkstart
 * @create 2022-10-16-12:11
 */
public class MyBinaryTree {
    //孩子兄弟表示法
    private static class Node {
        private char val;
        private Node left;
        private Node right;

        public Node(char val) {
            this.val = val;
        }
    }

    //生成一个测试二叉树
    public Node buildATree() {
        Node nodeA = new Node('A');
        Node nodeB = new Node('B');
        Node nodeC = new Node('C');
        Node nodeD = new Node('D');
        Node nodeE = new Node('E');
        Node nodeF = new Node('F');
        Node nodeG = new Node('G');
        Node nodeH = new Node('H');
        nodeA.left = nodeB;
        nodeA.right = nodeC;
        nodeB.left = nodeD;
        nodeB.right = nodeE;
        nodeE.left = nodeG;
        nodeG.right = nodeH;
        nodeC.right = nodeF;
        return nodeA;
    }

    //先序遍历（输出内容）
    //根左右
    //传入一个二叉树的根节点，根据先序遍历访问该树
    public void preOrder(Node root){
        if (root == null) {
            return;
        }
        //根
        System.out.print(root.val+",");
        //左树
        preOrder(root.left);
        //右树
        preOrder(root.right);
    }

    //中序遍历   左根右
    public void inOrder(Node root){
        if(root == null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val+",");
        inOrder(root.right);
    }
    //  后续遍历
    public void postOrder(Node root){
        if(root==null){
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+",");

    }

    /*
    传入一个二叉树根节点，求出二叉树的节点的个数
     */
    public int getNodeCount(Node root){
        if (root == null) {
            return 0;
        }
        return 1+ getNodeCount(root.left)+getNodeCount(root.right);
    }

    //传入根节点，就能求出叶子节点的个数
    public int getLeafNodeCount(Node root){

        //空树
        if(root==null){
            return 0;
        }
        //只有根节点
        if(root.left==null&&root.right==null){
            return 1;
        }
        //此时二叉树不为空且有子树
        //此时二叉树叶子节点的个数为  左树叶子节点个数+右数叶子节点个数
        return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);

    }
//    树的高度
    public int height(Node root){
        if(root==null){
            return 0;
        }
        return 1+Math.max(height(root.left),height(root.right));

    }

/*
判断一颗以root为根节点的二叉树是否包含值为val的节点
 */
    public boolean contains(Node root,char val){
        if(root==null){
            return false;
        }
        if(root.val==val){
            return true;
        }
            return contains(root.right, val)|| contains(root.left, val);

    }

    public int getKLeveNodes(Node root ,int k){
        if (k <= 0 || root == null) {
            return 0;
        }
        if (k == 1) {
            return 1;
        }
        return getKLeveNodes(root.left, k - 1) +
                getKLeveNodes(root.right, k - 1);
    }
    public static void main(String[] args) {
        MyBinaryTree myBinaryTree = new MyBinaryTree();
        Node root = myBinaryTree.buildATree();
        System.out.println("先序");
        myBinaryTree.preOrder(root);
        System.out.println();
        System.out.println("=====中序===");
        myBinaryTree.inOrder(root);
        System.out.println();
        System.out.println("=====后序===");
        myBinaryTree.postOrder(root);
        System.out.println("节点个数为"+myBinaryTree.getNodeCount(root));
        System.out.println("二叉树的叶子节点");
        System.out.println(myBinaryTree.getLeafNodeCount(root));
        System.out.println(myBinaryTree.contains(root,'H'));
        System.out.println(myBinaryTree.contains(root,'X'));

    }


}
